1. Field of the Invention
The present invention relates to a secret communication system and, more particularly, to a system and method for allowing a sender and a receiver to share secret information.
2. Description of the Related Art
The internet has become the economic and social infrastructure over which various data are exchanged. Therefore, it is an important issue to devise preventive measures to protect data flowing over networks from risks of eavesdropping. One of the preventive measures is a secret communication system by which data for communication is encrypted. For encryption methods, there are two kinds of schemes: secret-key cryptography and public key cryptography.
Secret-key cryptography, as is typified by AES (Advanced Encryption Standard), is a scheme that uses a common encryption key for both encryption and decryption, and is capable of high-speed processing. For this reason, this scheme is used to encrypt data itself.
On the other hand, public key cryptography, as is typified by RSA (Rivest Shamir Adleman), is a scheme based on a one-way function, using a public key for encryption and a private key for decryption. Since this scheme is not suitable for high-speed processing, it is used to distribute a cryptographic key for the secret key scheme.
In secret communication where secrecy is ensured by encrypting data, an important thing to ensure the secrecy is that encrypted data cannot be broken even if the encrypted data is intercepted by an eavesdropper. To do so, it is necessary not to consecutively use the same key for encryption. This is because the consecutive use of the same key for encryption may increase the possibility that the encryption key is estimated based on the increased amount of intercepted data.
Accordingly, it is required to update an encryption key shared between a sender and a receiver. It is indispensable that the key being updated is not intercepted and broken during key update. Therefore, to update the key, there are two broad types of methods: (1) a method in which the key is encrypted for transmission by the public key cryptography, and (2) a method in which the key is encrypted for transmission by using a master key that is a common key preset for key update. (For example, see Japanese Patent Application Unexamined Publication Nos. 2002-344438 and 2002-300158.) The security according to these methods depends on the fact that an enormous amount of calculation is required for cryptanalysis.
On the other hand, quantum key distribution (QKD) technology, unlike ordinary (classical) optical communications, is a technology that allows a sender and a receiver to generate and share a cryptographic key by the transmission of a single photon per bit. This is a cryptographic-key-sharing technology that makes eavesdropping impossible, which has been proved on the basis of quantum mechanics (see Bennett, C. H., and Brassard, G., “QUANTUM CRYPTOGRAPHY: PUBLIC KEY DISTRIBUTION AND COIN TOSSING” IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, Dec. 10-12, 1984, pp. 175-179 (hereinafter, this document will be referred to as Bennett and Brassard), and Ribordy, G., Gauiter, J., Gisin, N., Guinnard, O., and Zbinden, H., “Automated ‘plug & play’ quantum key distribution” Electron Letters, Vol. 34, No. 22 (1998), pp. 2116-2117). However, since no perfect single-photon sources exist yet, single-photon transmission is achieved in practice by attenuating coherent light so that the mean number of photons per pulse becomes one or smaller, that is, the probability of the presence of two or more photons per pulse is reduced.
Here, one of the most typical quantum key distribution algorithms, called the BB84 protocol, will be described briefly with reference to Bennett and Brassard.
FIG. 1 is a schematic diagram showing a concept of a quantum key distribution method according to the BB84 protocol. It is assumed here that Alice (sender) 141 and Bob (receiver) 143 are connected through an optical transmission line 142. According to this method, Alice 141 has two random number sources, one of which (random number 1) provides source data of a cryptographic key, and the other one of which (random number 2) provides bases. Alice 141 randomly performs any one of four types of modulation (0, π/2, π, 3π/2) on each single photon depending on a combination of the random numbers, and sends it to Bob 143.
On the other hand, Bob 143 has a random number source (random number 3) corresponding to bases. When a value of the random number 3 is “0,” Bob 143 performs a modulation of a phase of 0 (+basis) on a photon sent from Alice 141. When a value of the random number 3 is “1,” Bob 143 performs a modulation of a phase of π/2 (x basis) on a photon sent from Alice 141. Thus, when bases used for modulation at Alice 141 and Bob 143 are the same (random number 2=random number 3), Bob 143 can correctly detect a corresponding value of the random number 1 (random number 1=random number 4). When bases are different (random number 2≠random number 3), Bob 143 randomly obtains 0/1 as a value of the random number 4, independently of a value of the random number 1. Since each of the random numbers 1, 2 and 3 is a sequence of random numbers that vary with each one bit, the probability that a match of bases occurs and the probability that no match of bases occurs are both 50%. However, since those bits corresponding to non-matching bases are removed in basis reconciliation at a subsequent stage, Alice 141 and Bob 143 can share a bit string of 0s and 1s based on the random number 1.
FIG. 2 is a flowchart showing a flow of quantum key generation in general. As described above, through quantum key distribution, an output of 0 or 1 (raw key) is obtained depending on the difference between the depths of phase modulation at Alice and Bob, and thereafter, by checking part of the bases used, a string of bits (sifted key) corresponding to matching bases is shared (basis reconciliation). As regards a prior art, Japanese Patent Application Unexamined Publication No. 2000-174747 discloses a quantum cryptography device that allows a sender and a receiver to share a sifted key by using a quantum channel and a classical channel.
However, the bit string shared as described above contains errors attributable to the transmission line 142 and/or receiver. Accordingly, error correction processing is required to correct these errors. In addition to this, an error also occurs in the shared bit string when an eavesdropper present on the transmission line intercepts the photon information. Therefore, to share a cryptographic key for final use, not only the error correction processing to correct errors, but also privacy amplification processing is required to reduce the amount of information that can be supposed to have been intercepted, based on the frequency of errors (error rate).
(Error Correction)
For the error correction processing, for example, a method as described in Brassard, G., and Salvail, L., “Secret-key Reconciliation by Public Discussion” in Advances in Cryptology—EUROCRYPT '93 Proceedings, Lecture Notes in Computer Science, Vol. 765, PP. 410-423, can be employed. According to this method, error correction is performed in such a manner that a bit string as a sifted key is divided into a plurality of blocks in each of a sender and a receiver, a block containing an error is located by checking the parity of each block, and the error is corrected by, for example, applying a Hamming code to the block in question. In addition, on the assumption that an even number of errors might be contained in one block, the bit string is permuted at random, and then parity check and error correction are performed again. Such work is repeated multiple times (V times), thereby detecting an error remaining in the secret bit string. For example, assuming that the number of parity check bits is approximately half the number of the bits in the sifted key, when parity check is repeated V times, the probability that a remaining error cannot be detected is 1/2V or lower. Since V-bit information has been leaked to a third party by such release of parity bits, these V bits are discarded from the key. Through this error correction process, G-bit key information is assumed to remain.
(Privacy Amplification)
For the privacy amplification processing, a method as described in Bennett, C. H., Brassard, G., Crepeau, C., and Maurer, U. M., “Generalized Privacy Amplification” IEEE Transactions in Information Theory, Vol. 41, No. 6 (1995), pp. 1915-1923, can be employed. The privacy amplification processing is a process for generating new random numbers by removing the amount of information that has the possibility of being leaked during key distribution. Here, the G-bit key information is sifted to yield a key of F bits (F<G). A specific procedure is as follows.
Alice generates random numbers (parity-calculation bits) inside and, for the G-bit key information Alice maintains, calculates the parity of bits at positions designated by the generated random numbers. Alice sets the calculated parity bit as the first bit of a key and sends these random numbers (parity-calculation bits) to Bob. Based on the received random numbers, Bob calculates parity for the G-bit key information Bob maintains, and sets that parity bit as the first bit of a key. By repeating such work, as much information as conceivably intercepted on the way along the transmission line is discarded, thereby creating a new F-bit final key. An eavesdropper cannot gain knowledge of new random numbers (final key) after privacy amplification unless she knows all the parity-calculation bits.
In the case where privacy amplification processing as described above is performed on G-bit key information after error correction to generate as many new random numbers as F bits, the number of bits, F, corresponding to the new random numbers is represented by the following equation:F=G−eG−V−S. 
Here, e is the proportion of the information stolen by an eavesdropper intercepting the quantum communication. Therefore, it can be thought that the eavesdropper, Eve, possesses eG-bit information. V is the number of bits released in the process of remaining-error detection. S is a security parameter for privacy amplification. The larger the value of S, the closer to the perfect secrecy.
When an encryption key shared between a sender and a receiver is updated, there are several possible methods as described above, such as sending the updated key after encrypting it by the public key cryptography, or sending the updated key after encrypting it by using a common key preset for update. The security according to these methods is based on the fact that an enormous amount of calculation is required to break the encrypted key. Therefore, there has been a problem that the secrecy is degraded with improvement in cryptanalysis technology, such as improvement in computer power and improvement in cryptanalysis algorithms. For example, in the 56-bit DES challenge contests where teams compete in time to break DES (Data Encryption Standard), which is a common key cipher, although it took 96 days to break DES in 1997, the time was reduced to 22 hours in 1999. As for a public key cipher, although it took eight months to break a RSA public key cipher with a key length of 429 bits in 1994, it took about three months to break one with a key length of 576 bits in 2004. As described above, the cryptanalysis technology has been improving.
On the other hand, the quantum key distribution (QKD) technology has been studied and developed with an eye to implementing more secure systems. Accordingly, for the security of a key, attention has been focused only on the fact that whatever the attack, eavesdropping proves completely unsuccessful theoretically. For this reason, in QKD, the mean number of photons per pulse is fixed at 1.0 or smaller.
One of conceivable eavesdropping strategies in QKD is a photon-number splitting (PNS) attack, which is thought of as the most powerful attack at the present time. The PNS attack is a strategy in which one photon is stolen from a pulse including two or more photons, and further in the case of a pulse including one photon, information is stolen by entangling a photon. However, this strategy is difficult to realize, even unrealistic.
For a relatively realistic eavesdropping strategy, an intercept/resend attack is known in which Eve disguises herself as Bob to receive a signal from Alice and as Alice to send it on to Bob. If this eavesdropping is present, the error rate is, in principle, 25%. Also known is a strategy in which one photon is stolen from a pulse including two or more photons (beam splitting attack 1). However, according to this eavesdropping strategy, eavesdropping can be easily detected because the number of photons arriving at Bob is reduced. In addition, there is also a strategy in which an optical link from Alice to Bob is optically split at some point between Alice and Bob, and a part from this point to Bob is replaced with a lossless transmission link, thereby intercepting as much of the optical signal as is equivalent to the loss of transmission from the split point to Bob (beam splitting attack 2). However, this strategy is unrealistic in the lossless transmission link. Further, for another strategy that is difficult to realize, an individual (incoherent) attack is also known in which Eve entangles a photon with a photon being transmitted to copy the quantum state, thereby intercepting a small amount of information. If this individual (incoherent) attack only is applied, the amount of intercepted information does not depend on the number of photons. The above-mentioned PNS attack is the combination of the beam splitting attack 2 and the individual (incoherent) attack.
FIG. 3 is a graph schematically showing the relationship between the mean number of photons and the transmittable distance in a quantum key distribution system, for each different eavesdropping strategy. Each curve for its corresponding eavesdropping strategy indicates the border where, under the assumption that the eavesdropping strategy in question is performed, the amount of information shared between Alice and Bob becomes equal to the amount of information intercepted by Eve, in which case the key generation rate is zero. Where the transmission distance is longer than the distance indicated by the curve, the amount of intercepted information is larger, and it is impossible to generate a key. Where the transmission distance is shorter than the distance indicated by the curve, the amount of shared information is larger, and it is possible to generate a key. Additionally, the shorter the transmission distance, the higher the key generation rate.
From the viewpoint of the transmission distance, it is preferable to keep the mean number of photons per pulse much smaller than 1.0, in the case of seeking for the security at the level of beating the PNS attack. However, as can be seen from this graph, for the security at the level of beating the beam splitting attack 1, even if the mean number of photons is 1.0 to 4.0, it is possible to cover some transmission distance.
In other words, although it is necessary to set the number of photons per optical pulse at 1.0 or smaller in order to beat an attack of PNS class, the security of such highest level is not always required. Some users might put a higher priority on the transmission distance, key update rate, or amount of key, even if the security is sacrificed to some degree. In conventional quantum key distribution systems, it has been impossible to reflect a user request in the security of such an updated key.